One issue common to many data communications technologies is the corruption of data by noise in a communication channel. Thus, error detection and correction techniques are applied to reduce the data corruption. Many such techniques are implemented using forward error correction, i.e., redundant coding of the data prior to transmission. In general, forward error correction involves inserting data bits into the transmitted data stream that indicate whether an error is present in the received data stream. More complex codes provide the ability to deduce the true transmitted data from a received data stream despite the presence of errors.
Low Density Parity Check (LDPC) codes are error correction codes currently used in many high-speed communication standards, such as DVB-S2 (Digital video broadcasting), WiMAX (IEEE 802.16e standard for microwave communications), 10 GBase-T Ethernet (802.3an) and G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable). The LDPC codes used are binary linear block codes with a sparse parity-check matrix H, i.e., the matrix includes a low number of non-zero elements. The parity check matrix H is an m×n matrix, where n is the number of bits in a codeword and m is the number of redundancy bits (i.e., parity bits) of the coding scheme. Further, the location of a 1 in the parity-check matrix H indicates that a bit is involved in a parity check. The code rate R of an LPDC code is a unit of measure based on the number of information bits k and the number of parity bits m that may be contained in a generated codeword. More specifically, a code rate R is a ratio of the number of information bits k in a codeword to the total number of bits n in the codeword, i.e.,R=k/n For example, a code rate of ½ refers to a codeword in which half of the bits in the codeword are information bits and the other half are parity bits. Further, if the codeword length is 576 bits, the number of information bits k in a codeword generated with a code rate of ½ would be 288 and the number of parity bits m would also be 288.
A Tanner graph, which is a specific type of bipartite graph, may be used to represent a binary LDPC code. The Tanner graph representation has two kinds of nodes, variable nodes which represent the bits of a codeword and check nodes which represent the set of parity-check constraints, i.e., a parity check equation, defining the LDPC code. Each column of the parity check matrix H represents a variable node, and each row represents a check node. A variable node and column of H are referred to interchangeably as are a check node and row of H. Edges in the graph connect variable nodes to check nodes and each pair of nodes is connected by at most one edge. The number of edges in the graph equals the number of ones in the parity check matrix H.
Many of the communication standards specify structured LDPC codes. Instead of specifying a large m×n parity check matrix H, the design of a structured LDPC code starts with a smaller mb×nb base matrix Hb, makes z copies of the base matrix Hb, and interconnects the copies to form an m×n parity check matrix H, where m=mb×z and n=nb×z. A parity check matrix H is derived from the base parity check matrix Hb by replacing each 1 in the base parity check matrix Hb with a z×z permutation submatrix and each 0 with a z×z submatrix of all zeroes. In essence, each edge in the base parity check matrix Hb is mapped to a vector edge of length z in the parity check matrix H, each variable node of the base parity check matrix Hb is mapped to a vector variable node of length z in the parity check matrix H, and each check node of the base parity check matrix Hb is mapped to a vector check node of length z in the parity check matrix H. Each z×z permutation submatrix is defined as a circular shift of the columns of a z×z identity matrix by some amount.
By using different values of z, i.e., the expansion factor, LDPC codes of rate kb/nb, where kb=nb−mb, can be specified for different information bit sequence sizes k=z*kb from a single base parity check matrix Hb. In addition, a parity check matrix H can be represented in implementations of encoders and decoders by an mb×nb base parity check matrix Hb in which a −1 denotes a z×z all-zero submatrix, a 0 denotes a z×z identity matrix, and any other number denotes a z×z permutation matrix that is a z×z identity matrix circularly shifted by that number. Further, encoding and decoding can be performed based on the smaller mb×nb base parity check matrix Hb and vectors of z bits.
In general, decoding algorithms for LDPC codes are iterative, message passing algorithms in which at each iteration messages representing estimates of bit values of the codeword being decoded are passed from variable nodes to check nodes and from check nodes to variable nodes along the edges of the graph. The messages passed from variable nodes to check nodes are computed based on the observed value of the variable node and some of the messages passed from neighboring check nodes to the variable node. Further, a message sent from a variable node to a check node must not be based on the message sent in the previous round from the check node to the variable node. Similarly, a message sent from a check node to a variable node must not be based on the message sent in the previous round from the variable node to the check node. Messages are exchanged, i.e., the decoding process iterates, until a codeword is detected or a maximum number of iterations is performed.
One message passing algorithm used frequently for LDPC decoding is belief propagation. In belief propagation, the messages transmitted along the edges of the graph represent probabilities, i.e., beliefs. More specifically, a message from a variable node to a check node represents the probability that the variable node, i.e., the bit of the codeword represented by the variable node, has a certain value given the observed value of the variable node and all the values in the messages passed to the variable node from check nodes in the previous iteration. Further, a message from a check node to a variable node represents the probability that the variable node has a certain value given all the messages passed to the check node from other variable nodes in the previous iteration.
In operation, the belief propagation algorithm initially assigns each variable node in the graph a received value that is an estimate of the value of the associated bit as determined by observation of the communications channel. During an iteration of the algorithm, bit probability messages are passed from the variable nodes to the check nodes, updated, and sent back and summed at the variable nodes. The computations in each iteration involve both a row update and a column update of the parity check matrix. The row update involves processing an equation for each edge that enters a check node and permutation of the data after it is read from memory. The column update involves summing the check nodes to form the variable nodes and storing the permutated data in a unique order as defined by the encoder generator matrix. The iterations are repeated until the parity check matrix is satisfied, i.e., all parity check rows are zero, or some other convergence criteria is reached, or until some maximum number of iterations is executed.
Thus, LPDC decoding is computationally complex. In addition, the number of check nodes and variable nodes may be on the order of hundreds or thousands. Further, LDPC decoders may need to process many iterations. Decoding termination algorithms using matrix mathematics may also be required, which involve additional computations and resources. Accordingly, improvements in decoding LDPC codes are desirable.